%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  TP 2 - Programación Lógica  %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%% Integrantes %%%%%%%%%%%
%%%% Pablo del Sel
%%%% Marcos Navarro




%% Rutas aéreas predefinidas.

% llega(?origen, ?destino, ?tiempo)
llega(buenos_aires, mdq, 1).
llega(buenos_aires, cordoba, 2).
llega(buenos_aires, rio, 4).
llega(buenos_aires, madrid, 12).
llega(buenos_aires, atlanta, 11).
llega(mdq, buenos_aires, 1).
llega(cordoba, salta, 1).
llega(salta, buenos_aires, 2).
llega(rio, buenos_aires, 4).
llega(rio, new_york, 10).
llega(atlanta, new_york, 3).
llega(new_york, madrid, 9).
llega(madrid, lisboa, 1).
llega(madrid, buenos_aires, 12).
llega(lisboa, madrid, 1).
llega(new_york, buenos_aires, 11).

%% Aviones y sus autonomías.

% autonomia(?avion, ?horas)
autonomia(boeing_767, 15).
autonomia(airbus_a320, 9).
autonomia(boeing_747, 10).






%% Predicados pedidos:


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ciudades(-Ciudades)
%
% Ciudades será un conjunto (lista sin repetidos) de las ciudades
% que son orígen en los predicados 'llega' 

ciudades(Ciudades) :-
		setof(Origen, Destino^Tiempo^llega(Origen, Destino, Tiempo), Ciudades).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% viajeDesde(+Origen, ?Destino, -Recorrido, -Tiempo) -- Devuelve infinitos resultados.
%
% Para cada Longitud (entre 0 e infinito) genera todos los Recorridos posibles
% entre Origen y Destino de esa longitud exacta, y calcula el Tiempo de viaje

viajeDesde(Origen, Destino, Recorrido, Tiempo) :-
		between(0, inf, Longitud),
		viajeDeLongitud(Origen, Destino, Recorrido, Tiempo, Longitud).


% Predicados Auxiliares

% viajeDeLongitud(?Origen, ?Destino, -Recorrido, -Tiempo, +Longitud)
% Genera todos los posibles Recorridos (y calcula el Tiempo de viaje) entre Origen y Destino
% de longitud Longitud

% Predicado base (viajes de longitud 0):
% el recorrido es un singleton con cada una de las posibles ciudades (sin repetidos)

viajeDeLongitud(Origen, Origen, [Origen], 0, 0) :-
		ciudades(Ciudades),
		member(Origen, Ciudades).

% Predicado recursivo (viajes de longitud mayor a 0):
% Define una ciudad en la que se hace una Escala inmediata anterior al Destino,
% se genera el recorrido desde el Orígen hasta dicha Escala y luego se los une para generar el
% Recorrido y Tiempo finales

viajeDeLongitud(Origen, Destino, Recorrido, Tiempo, Longitud) :-
		Longitud > 0,
		LongitudHastaEscala is Longitud - 1,
		viajeDeLongitud(Origen, Escala, RecorridoHastaEscala, TiempoHastaEscala, LongitudHastaEscala),
		llega(Escala, Destino, TiempoDesdeEscala),
		append(RecorridoHastaEscala, [Destino], Recorrido),
		Tiempo is TiempoHastaEscala + TiempoDesdeEscala.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% viajeSinCiclos(+Origen, ?Destino, -Recorrido, -Tiempo)
%
% De forma similar al anterior, pero la longitud de los Recorridos está acotada
% por la cantidad de ciudades

viajeSinCiclos(Origen, Destino, Recorrido, Tiempo) :-
		ciudades(Ciudades),
		length(Ciudades, CantCiudades),
		between(0, CantCiudades, Longitud),
		viajeSinCiclosDeLongitud(Origen, Destino, Recorrido, Tiempo, Longitud).


% Predicados Auxiliares

% viajeSinCiclosDeLongitud(?Origen, ?Destino, -Recorrido, -Tiempo, +Longitud)
% Genera Recorridos de longitud Longitud de forma similar al ej anterior, pero verificando que
% cada ciudad Destino (corresponden a las distintas Escalas) no pertenezca al recorrido previo

viajeSinCiclosDeLongitud(Origen, Origen, [Origen], 0, 0) :-
		ciudades(Ciudades),
		member(Origen, Ciudades).

viajeSinCiclosDeLongitud(Origen, Destino, Recorrido, Tiempo, Longitud) :-
		Longitud > 0,
		LongitudHastaEscala is Longitud - 1,
		viajeSinCiclosDeLongitud(Origen, Escala, RecorridoHastaEscala, TiempoHastaEscala, LongitudHastaEscala),
		llega(Escala, Destino, TiempoDesdeEscala),
		%%% Destino no debe pertenecer al recorrido previo
		delete(RecorridoHastaEscala, Destino, RecorridoHastaEscala),
		append(RecorridoHastaEscala, [Destino], Recorrido),
		Tiempo is TiempoHastaEscala + TiempoDesdeEscala.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% viajeMasCorto(+Origen, +Destino, -Recorrido, -Tiempo)
%
% Generate: todos los viajes sin ciclos (el mínimo no los va a tener porque no hay pesos negativos)
% Test: los que tengan duración igual al mínimo (calculado en minimoTiempoDeViaje)

viajeMasCorto(Origen, Destino, Recorrido, Tiempo) :-
	viajeSinCiclos(Origen, Destino, Recorrido, Tiempo),
	minimoTiempoDeViaje(Origen, Destino, Tiempo).


% Predicados Auxiliares

% minimoTiempoDeViaje(+Origen, +Destino, -Tiempo)
% Generate: una lista con los tiempos de todos los viajes sin ciclos 
% Test: Tiempo es el mínimo de la lista

minimoTiempoDeViaje(Origen, Destino, Tiempo) :-
		findall(T, viajeSinCiclos(Origen, Destino, _, T), Tiempos),
		min_list(Tiempos, Tiempo).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% grafoCorrecto
%
% Verifica que todas las ciudades sean alcanzables a partir de una cualquiera y viceversa

grafoCorrecto :-
		todasLasCiudades([Ciudad|Ciudades]),
		ciudadesConexas(Ciudad, [Ciudad|Ciudades]).


% Predicados Auxiliares

% todasLasCiudades(-Ciudades)
% Ciudades es un conjunto de todas las ciudades del grafo, tanto las que son orígen
% en los predicados 'llega' como las que son destino

todasLasCiudades(Ciudades) :-
		ciudades(Origenes),
		setof(Destino, Origen^Tiempo^llega(Origen, Destino, Tiempo), Destinos),
		union(Origenes, Destinos, Ciudades).


% ciudadesConexas(+Origen, -Ciudades)
% Ciudades es el conjunto de las ciudades que son alcanzables y alcanzan la ciudad de Orígen

ciudadesConexas(Origen, Ciudades) :-
		setof(Ciudad, puedoIrYVolver(Origen, Ciudad), Ciudades).


% puedoIrYVolver(+Origen, +Destino)

puedoIrYVolver(Origen, Destino) :-
		viajeSinCiclos(Origen, Destino, _, _),
		viajeSinCiclos(Destino, Origen, _, _).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% cubreDistancia(+Recorrido, ?Avion)

% casos donde el recorrido es trivial
cubreDistancia([], _).
cubreDistancia([_], _).

% caso con recorrido de dos o más ciudades
cubreDistancia([Origen | [Destino | Recorrido]], Avion) :-
		llega(Origen, Destino, Tiempo),
		autonomia(Avion, Autonomia),
		Autonomia >= Tiempo,
		cubreDistancia([Destino | Recorrido], Avion).


% test

test_vuelo(Origen, Destino, Recorrido, Avion) :-
	viajeSinCiclos(Origen, Destino, Recorrido, _),
	cubreDistancia(Recorrido, Avion).



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vueloSinTransbordo(+Aerolinea, +Ciudad1, +Ciudad2, ?Tiempo, ?Avion)

% No se consideran deseadas las soluciones repetidas, entendiendose por esto a recorridos distintos
% de un mismo avión que tarden lo mismo

vueloSinTransbordo(Aerolinea, Ciudad1, Ciudad2, Tiempo, Avion) :-
		esAerolinea(Aerolinea),
		avionEnCiudad(Aerolinea, Ciudad1, Avion),
		once(cubreViajeMasCorto(Ciudad1, Ciudad2, Tiempo, Avion)).


cubreViajeMasCorto(Ciudad1, Ciudad2, Tiempo, Avion) :-
		viajeMasCorto(Ciudad1, Ciudad2, Recorrido, Tiempo),
		cubreDistancia(Recorrido, Avion).



esAerolinea([]).
esAerolinea([(Ciudad, Aviones) | Aeropuertos]) :-
		todasLasCiudades(Ciudades),
		once(member(Ciudad, Ciudades)),
		avionesValidos(Aviones),
		esAerolinea(Aeropuertos).


avionesValidos([]).
avionesValidos([Avion | Aviones]) :-
		autonomia(Avion, _),
		avionesValidos(Aviones).


avionEnCiudad([(Ciudad, Aviones) | _], Ciudad, Avion) :-
		member(Avion, Aviones).

avionEnCiudad([(OtraCiudad, _) | Aerolinea], Ciudad, Avion) :-
		Ciudad \= OtraCiudad,
		avionEnCiudad(Aerolinea, Ciudad, Avion).



test_aerolinea :-
		aerolinea(A),
		esAerolinea(A).

test_avion :-
		aerolinea(A),
		avionEnCiudad(A, lisboa, boeing_747).

test_sin_transbordo(Ciudad1, Ciudad2, Tiempo, Avion) :-
		aerolinea(A),
		vueloSinTransbordo(A, Ciudad1, Ciudad2, Tiempo, Avion).

aerolinea(A) :- A = [(buenos_aires, [boeing_767, boeing_747]), (madrid, [boeing_767, airbus_a320]),
		(rio, [airbus_a320]), (new_york, []), (lisboa, [boeing_767, boeing_747, airbus_a320])].





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pruebas

